﻿#include <iostream>
#include <queue>
#include <vector>
using namespace std;

struct ListNode 
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
 
class Solution
{
    struct cmp
    {
        bool operator()(ListNode* l1, ListNode* l2)
        {
            return l1->val > l2->val;
        }
    };

public:
    // 23. 合并 K 个升序链表
    // 利用优先级队列做优化
    // O(n*k*logk)
    ListNode* mergeKList(vector<ListNode*>& lists)
    {
        // 创建小根堆
        priority_queue<ListNode*, vector<ListNode*>, cmp> heap;

        // 把所有头节点加入小根堆
        for (auto l : lists)
            if (l)
                heap.push(l);

        // 合并k个有序链表
        ListNode* ret = new ListNode(-1);
        ListNode* prev = ret;
        while (!heap.empty())
        {
            ListNode* t = heap.top();
            heap.pop();
            prev->next = t;
            prev = t;
            if (t->next)
                heap.push(t->next);
        }

        prev = ret->next;
        delete ret;
        return prev;
    }

    // 归并
    ListNode* mergeKLists(vector<ListNode*>& lists)
    {
        return merge(lists, 0, lists.size() - 1);
    }

    ListNode* merge(vector<ListNode*>& lists, int left, int right)
    {
        if (left > right)
            return nullptr;
        if (left == right)
            return lists[left];

        int mid = (right - left) / 2 + left;
        ListNode* l1 = merge(lists, left, mid);
        ListNode* l2 = merge(lists, mid + 1, right);

        return mergeTowList(l1, l2);
    }

    ListNode* mergeTowList(ListNode* l1, ListNode* l2)
    {
        if (l1 == nullptr)
            return l2;
        if (l2 == nullptr)
            return l1;

        ListNode head;
        ListNode* cur1 = l1, * cur2 = l2, * prev = &head;
        while (cur1 && cur2)
        {
            if (cur1->val <= cur2->val)
            {
                prev->next = cur1;
                prev = cur1;
                cur1 = cur1->next;
            }
            else
            {
                prev->next = cur2;
                prev = cur2;
                cur2 = cur2->next;
            }
        }
        if (cur1)
            prev->next = cur1;
        if (cur2)
            prev->next = cur2;

        return head.next;
    }
};

int main()
{


    return 0;
}